#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = -1;
        int right = nums.size();
        int i = 0;
        int begin = 0;
        int end = nums.size()-1;


        while (1)
        {
            int key = nums[left + 1];

            while (i < right)
            {

                if (nums[i] < key)
                {
                    swap(nums[++left], nums[i]);
                    i++;
                }
                else if (nums[i] > key)
                {
                    swap(nums[--right], nums[i]);
                }
                else
                {
                    i++;
                }
            }
            int a, b, c;
            a = left - begin + 1;
            b = right - left - 1;
            c = end - right+1;

            if (c >= k)
            {
                begin = right;
                left = right - 1;
                i = right;
                right = nums.size();
            }
            else if (b + c >= k)
                return nums[left + 1];
            else
            {
                end = left;
                right = left + 1;
                left = begin-1;
                i = begin;
                k = k - b - c;
            }
        }


    }
};
int main()
{
    vector<int> nums = { 3,2,1,5,6,4 };
    Solution s;
    int ret = s.findKthLargest(nums, 2);
    cout << ret << endl;
    return 0;
}
//#include "test.h"
//
//void func()
//{
//	extern int i = 100;
//	cout << i << endl;
//}
//int main()
//{
//	//extern int i = 12;
//	cout << j << endl;
//	return 0;
//}